package com.vans.practice.alghr;

import java.util.Arrays;
/**
 * @Description: 堆排序
 * @Note: 不稳定
 * @平均时间复杂度：nLog2N
 * @空间复杂度： nLog2N
 * @Author elle
 * @Date 2020/10/14 11:55
 */
public class Heap {
    public static void main(String[] args) {
//        int[] arr = {5, 1, 7, 3, 1, 6, 9, 4};
        int[] arr = {140, 6, 7, 3, 20, 17};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {
        //初始化堆调整(从第一个非叶子节点开始调整, 从右到左. 从下往上)
        for (int i = (arr.length-1)/2; i >=0 ; i--) {
            ajustHeap(arr, i, arr.length);
        }
        for (int i = arr.length-1; i >=0 ; i--) {
            //交换堆头和尾元素
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            //  移除堆尾元素, 重新调整堆
            ajustHeap(arr, 0, i);
        }
    }

    /**
     * 调整堆, 从根节点i开始往下调整堆
     * @param arr
     * @param i
     */
    private static void ajustHeap(int[] arr, int i, int len) {
        //左孩子节点
        int lChild = 2 * i + 1;
        //父节点
        int parent = i;
        while (lChild < len) {
            int rChild = lChild + 1;
            if (rChild < len && arr[rChild] > arr[lChild]) {
                lChild ++;
            }
            if (arr[lChild] < arr[parent]) break;
            if (arr[lChild] > arr[parent]) {
                //交换根节点和叶子节点的值
                int temp = arr[parent];
                arr[parent] = arr[lChild];
                arr[lChild] = temp;
                parent = lChild;
                lChild = 2 * parent + 1;
            }
        }
        //如果右孩子存在, 判断左右孩子节点值的大小, 如果右孩子大, 则

    }
}
